# 十三届2022年复习
import math


def find_integer():
    """寻找整数"""
    res = []
    for i in range(11 * 17, 1000000000000000, 11 * 17):
        if i % 12 == 5 and i % 13 == 10 and i % 14 == 11 and i % 15 == 14 and i % 16 == 9 and \
                i % 18 == 11 and i % 19 == 18 and i % 20 == 9 and i % 21 == 11 and i % 22 == 11:
            res.append(i)
        if len(res) >= 2:
            break

    base = res[1] - res[0]
    for i in range(res[1] + base, 100000000000000000, base):
        if i % 31 == 27 and i % 32 == 25 and i % 33 == 11 and i % 34 == 17 and i % 35 == 4 and \
                i % 23 == 15 and i % 24 == 17 and i % 25 == 9 and i % 26 == 23 and i % 27 == 20 and \
                i % 36 == 29 and i % 37 == 22 and i % 38 == 37 and i % 39 == 23 and i % 40 == 9 and i % 29 == 16 and \
                i % 41 == 1 and i % 42 == 11 and i % 43 == 11 and i % 44 == 33 and i % 45 == 29 and i % 30 == 29 and \
                i % 46 == 15 and i % 47 == 5 and i % 48 == 41 and i % 49 == 46 and i % 28 == 25:
            return i


def count_prime_factor(num):
    """质因数个数"""
    cnt = 0
    i = 2
    while i * i <= num:
        if num % i == 0:
            cnt += 1
            while num % i == 0:
                num = num // i
        if i % 2 == 0:
            i += 1
        else:
            i += 2
    if num > 1:
        cnt += 1
    return cnt


def max_attack(n, m, inits, decays):
    """技能升级"""
    res = 0
    for i in range(m):
        add = max(inits)
        idx = inits.index(add)
        res += add
        inits[idx] -= decays[idx]
    return res


def prime_count():
    """小蓝做实验"""

    def sieve(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(math.sqrt(n)) + 1):
            if is_prime:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False

        return {idx for idx, is_p in enumerate(is_prime) if is_p}

    primes = sieve(int(1e8))
    errs = set()
    corrects = set()
    with open("../data/2022_a.txt", "r") as file:
        s = file.readline()
        while s or s != "\n":
            num = int(s)
            if num < 1e7 or num > 1e8:
                errs.add(num)
            else:
                corrects.add(num)
            s = file.readline()

    cnt = 0
    for num in corrects:
        if num in primes:
            cnt += 1

    for num in errs:
        is_prime = True
        for prime in primes:
            if num % prime == 0:
                is_prime = False
                break
        if is_prime:
            cnt += 1

    return cnt


def max_match_num(n):
    """火柴棒数字"""
    costs = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # 每个数字需要花费的火柴数量
    # 表示当前的选取状态, 用于比较大小, 等价于value
    # 例如当前选取10个9和7个8 那么state=(17,10,7,...)
    dp = [(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)] * (n + 1)
    for i in range(0, 10):  # 遍历每个数字
        weight = costs[i]
        for j in range(n, -1, -1):  # 逆序遍历每个背包的重量, 确保不会超过数量
            for k in range(1, 11):  # 遍历每个数字最多可以选择的次数
                if j >= weight * k:
                    state_o = dp[j]
                    state_n = list(dp[j - weight * k])
                    state_n[0] += k
                    idx = 10 - i
                    state_n[idx] = k
                    state_n = tuple(state_n)
                    if state_n > state_o:
                        dp[j] = tuple(state_n)
                else:
                    break
    res = ""
    for i in range(1, 11):
        res = res + (str(10 - i) * dp[n][i])
    return res


def sim_GCD(g: int, arr: list[int]):
    """近似GCD"""
    n = len(arr)
    start, end = 0, 1
    res = 0
    # cnt = arr[start] % g == 0 +
    while start < n - 1:
        pass


def min_count_one(n):
    """最少的1"""
    if n == 1 or n == 0:
        return n
    dist = [float('inf')] * n
    stack = [(1, 1)]  # (1的个数, 余数)

    while stack:
        cnt, rem = stack.pop()
        if cnt > dist[rem]:
            continue

        for i in [0, 1]:
            new_rem = (rem * 2 + i) % n
            new_cnt = cnt + i
            if new_cnt < dist[new_rem]:
                dist[new_rem] = new_cnt
                stack.append((new_cnt, new_rem))

    return dist[0]


def city_cleanliness(D: list[list[int]], L: list[list[int]], Q: int) -> int:
    # 环境治理
    n = len(D)

    def floyd(temp):
        nonlocal L

        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if temp[i][j] > temp[i][k] + temp[k][j]:
                        temp[i][j] = temp[i][k] + temp[k][j]

        return sum(sum(temp[i]) for i in range(n))

    def clean(day):
        cycle = day // n
        rem = day % n
        temp = [[D[i][j] for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                if i < rem:
                    temp[i][j] -= 1
                    temp[j][i] -= 1
                temp[i][j] = max(L[i][j], temp[i][j] - cycle)
                temp[j][i] = max(L[j][i], temp[j][i] - cycle)
        return temp

    p = float('inf')
    day = 0
    while p > Q:
        t = clean(day)
        p = floyd(t)
        day += 1
    return day - 1


if __name__ == '__main__':
    print(city_cleanliness([[0, 2, 4], [2, 0, 1], [4, 1, 0]], [[0, 2, 2], [2, 0, 0], [2, 0, 0]], 10))
